/**
 * 
 */
package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Michael
 *
 */
public class PrintAllSubsets {

    public static void allSubsetsIterative(int[] s) {
        int n = 1 << s.length; // number of subset

        for (int i = 0; i < n; ++i) {
            // use each bit in i to determine whether to print the
            // corresponding number in s
            for (int shift = 0; shift < s.length; ++shift) {
                if (((i >> shift) & 1) == 1) { // check each bit in i
                    System.out.printf("%d ", s[shift]);
                }
            }
            System.out.println();
        }
    }

    public static void allSubsetsRecursive(int[] s, int index, boolean[] output) {
        if (s.length == index) {
            for (int i = 0; i < s.length; ++i) {
                if (output[i])
                    System.out.printf("%d ", s[i]);
            }
            System.out.println();
        } else {
            output[index] = false;
            allSubsetsRecursive(s, index + 1, output);
            output[index] = true;
            allSubsetsRecursive(s, index + 1, output);
        }
    }

    public static void allSubsetsRecursive(int[] a, int index, StringBuilder sb) {
        if (a.length == index) {
            System.out.println(sb.toString());
        } else {
            allSubsetsRecursive(a, index + 1, sb);
            allSubsetsRecursive(a, index + 1, sb.append(a[index]));
            sb.setLength(sb.length() - 1);
        }
    }

    public static void allSubsetsRecursive(int[] a, int index, String s) {
        if (a.length == index) {
            System.out.printf("%s\n", s);
        } else {
            allSubsetsRecursive(a, index + 1, s);
            allSubsetsRecursive(a, index + 1, s + a[index]);
        }
    }

    public static void allSubsetsWithoutDuplicates(int[] s) {
        Arrays.sort(s);
        allSubsetsWithoutDuplicates(s, 0, new ArrayList<Integer>());
    }

    public static void allSubsetsWithoutDuplicates(int[] s, int index,
            List<Integer> l) {
        if (s.length == index) {
            for (int i : l) {
                System.out.printf("%d ", i);
            }
            System.out.println();
        } else {
            int count = 0;
            for (int i = index; i < s.length && s[i] == s[index]; ++i) {
                count++;
            }
            l.add(s[index]);
            allSubsetsWithoutDuplicates(s, index + count, l);
            l.remove(l.size() - 1);
            allSubsetsWithoutDuplicates(s, index + count, l);
        }
    }

    public static void allSubsetsWithoutOutputDuplicates(int[] s) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : s) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }
        Integer[] keys = map.keySet().toArray(new Integer[0]);
        allSubsetsWithoutOutputDuplicatesHelper(map, keys, 0,
                new StringBuilder());
    }

    public static void allSubsetsWithoutOutputDuplicatesHelper(
            Map<Integer, Integer> counts, Integer[] keys, int index,
            StringBuilder sb) {
        if (counts.size() == index) {
            System.out.printf("%s\n", sb.toString());
        } else {
            int key = keys[index];
            for (int i = 0, count = counts.get(key); i <= count; ++i) {
                for (int j = 0; j < i; ++j) {
                    sb.append(key);
                }
                allSubsetsWithoutOutputDuplicatesHelper(counts, keys,
                        index + 1, sb);
                sb.setLength(sb.length() - i);
            }
        }
    }

    public static void allSubsetsWithoutOutputDuplicatesHelper(
            Map<Integer, Integer> counts, Integer[] keys, int index, String s) {
        if (index == counts.size()) {
            System.out.printf("%s\n", s);
        } else {
            int key = keys[index];
            for (int i = 0, count = counts.get(key); i <= count; ++i) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < i; ++j) {
                    sb.append(key);
                }
                allSubsetsWithoutOutputDuplicatesHelper(counts, keys,
                        index + 1, s + sb.toString());
            }
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] set = new int[] { 1, 1, 2 };
        boolean[] output = new boolean[] { false, false, false, false };
        //allSubsetsIterative(set);
        //allSubsetsRecursive(set, 0, output);
        //allSubsetsRecursive(set, 0, new StringBuilder());
        //allSubsetsRecursive(set, 0, "");
        allSubsetsWithoutOutputDuplicates(set);
    }

    /**
     * 
     */
    public PrintAllSubsets() {
        // TODO Auto-generated constructor stub
    }

}
